package leetcode_800;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 *@author 周杨
 *SwapAdjacentInLRString_777 一个字符串只含X L R 一次转换是指将XL->LX 或者XR ->RX
 *describe:用广度搜素会超时  观察目标字符串 X是最关键的 因为X可以转换任意字符到这个位置 那么就找X出现的规律 AC 23%
 *2018年10月20日 上午10:30:26
 */
public class SwapAdjacentInLRString_777 {
	
	public boolean canTransform(String start, String end) {
        if(start.equals(end)) return true;
        if (start.length() != end.length()) return false;  
        if (!start.replace("X", "").equals(end.replace("X", ""))) return false;
        //这是本算法的关键 如果所有的X被替换掉 都无法相等 那么两个字符串肯定不等
        int p1 = 0;
        int p2 = 0;
        char[] ch1 = start.toCharArray();
        char[] ch2 = end.toCharArray();
        while (p1 < start.length()) {           
            while (p1 < ch1.length && ch1[p1] == 'X') p1++;
            while (p2 < ch2.length && ch2[p2] == 'X') p2++;
            if (p1 == ch1.length || p2 == ch2.length) return true;    //为什么一定此时正确 那么因为LR的顺序是固定的 在一定范围内随意调整  
            if (ch1[p1] == 'R' && p1 > p2) return false;//表示这个状态反转不过来了
            if (ch1[p1] == 'L' && p1 < p2) return false;
            p1++;
            p2++;
        }
        
        return true;
    }
	
	
	/**
	 * describe:广度优先遍历 超时 主要原因进行太多无效匹配
	 * 2018年10月20日 上午10:05:26
	 */
	public boolean canTransform1(String start, String end) {
        if(start.equals(end)) return true;
        Set<String> set=new HashSet<String>();//状态去重
        set.add(start);
        Queue<String> queue=new LinkedList<String>();
        queue.offer(start);
        while(!queue.isEmpty()) {
        	int size=queue.size();
        	for(int i=0;i<size;++i) {
        		String now=queue.poll();
        		char []chars=now.toCharArray();
        		for(int j=0;j<chars.length-1;++j) {
        			if(chars[j]=='X'&&chars[j+1]=='L') {
        				chars[j]='L';
        				chars[j+1]='X';
        				String newStr=new String(chars);
        				if(newStr.equals(end)) return true;
        				if(set.add(newStr)) queue.offer(newStr);
        				chars[j]='X';
        				chars[j+1]='L';//回溯
        			}
        			else if(chars[j]=='R'&&chars[j+1]=='X') {
        				chars[j]='X';
        				chars[j+1]='R';
        				String newStr=new String(chars);
        				if(newStr.equals(end)) return true;
        				if(set.add(newStr)) queue.offer(newStr);
        				chars[j]='R';
        				chars[j+1]='X';//回溯
        			}
        		}
        	}
        }
        return false;
    }
}
